/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 62536
 * Date: 2024-06-01
 * Time: 20:00
 */
public class Solution {public int numDecodings(String s) {
    int n = s.length();
    char[] arr = s.toCharArray();
    int[] dp = new int[n];

    //初始化
    if(arr[0] != '0'){
        dp[0] = 1;
    }
    if(n == 1){
        return dp[0];
    }

    if(arr[1] != '0' && arr[0] !='0'){
        dp[1] += 1;
    }

    int a = (arr[0] - '0') * 10 + (arr[1] - '0');
    if(a <= 26 && a >= 10){
        dp[1] += 1;
    }

    //填表
    for(int i = 2; i < n; i++){
        if(arr[i] != '0'){
            dp[i] += dp[i-1];
        }
        int b = (arr[i-1] - '0') * 10 + (arr[i] - '0');
        if(b <= 26 && b >= 10){
            dp[i] += dp[i-2];
        }
    }

    return dp[n-1];

}

}
